package com.zhang.list;


/**
 * 动态数组
 *
 * @param <E> 泛型
 */
public class ArrayList<E> implements List<E> {
    private int size;

    private E[] elements;

    /**
     * 设置默认的初始化空空间
     */
    private static final int CAPACITY_DEFAULT = 5;

    /**
     * 元素不存在
     */
    private static final int ELEMENT_NOF_FOUND = -1;

    public ArrayList(int capacity) {
        capacity = capacity < CAPACITY_DEFAULT ? CAPACITY_DEFAULT : capacity;
        elements = (E[]) new Object[capacity];
    }

    public ArrayList() {
        this(CAPACITY_DEFAULT);
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOF_FOUND;
    }

    @Override
    public void add(E element) {
        add(size, element);
    }

    @Override
    public E get(int index) {
        // O(1)
        rangeCheck(index);
        return elements[index];
    }

    @Override
    public E set(int index, E element) {
        // O(1)
        rangeCheck(index);
        E oldElement = elements[index];
        elements[index] = element;
        return oldElement;
    }

    @Override
    public void add(int index, E element) {
        /**
         * 最好: O(1)
         * 最坏: O(n)
         * 平均: O(n) (1+2+3+....+n)/n
         */
        // 范围检查
        rangeCheckForAdd(index);
        // 确保扩容
        ensureCapacity();
        // 移动数据,从后开始迁移
        for (int i = size; i > index; i--) {
            elements[i] = elements[i - 1];
        }
        // 设置元素
        elements[index] = element;
        size++;
    }

    /**
     * 确保数组的扩容
     */
    private void ensureCapacity() {
        // 获取数组的长度
        int oldLength = elements.length;
        // 如果当前容量小于数组的长度
        if (size + 1 < oldLength) {
            return;
        }
        // 需要扩容,设置新的长度
        int newCapacity = oldLength + (oldLength >> 1);
        // 创建新数组
        E[] newElements = (E[]) new Object[newCapacity];
        // 数据迁移到新数组
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
    }

    @Override
    public E remove(int index) {
        /**
         * 最好: O(1)
         * 最坏: O(n)
         * 平均: O(n) (1+2+3+....+n)/n
         */
        // 范围检查
        rangeCheck(index);
        E oldElement = elements[index];
        // 数据往前移
        for (int i = index; i < size - 1; i++) {
            elements[index] = elements[i + 1];
        }
        // 将最后一个值为空
        elements[--size] = null;
        return oldElement;
    }

    @Override
    public int indexOf(E element) {
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (elements[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (element.equals(elements[i])) {
                    return i;
                }
            }
        }

        return ELEMENT_NOF_FOUND;
    }

    @Override
    public void clear() {
        // 将所有位置置为空
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    /**
     * 添加元素的index 范围校验
     *
     * @param index index位置
     */
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0) {
            throw new IndexOutOfBoundsException(outOfIndexMsg(index));
        }
    }

    /**
     * index 范围校验
     *
     * @param index index位置
     */
    private void rangeCheck(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException(outOfIndexMsg(index));
        }
    }

    /**
     * 通过index构造index不合法的提示信息
     */
    private String outOfIndexMsg(int index) {
        return "Index: " + index + ", size:" + size;
    }

    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("size = ").append(size).append(", [");
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(",");
            }
            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }
}
